package com.lc202407;

import java.util.*;
import java.util.stream.Collectors;

/**
 * [["John","johnsmith@mail.com","john_newyork@mail.com"],
 * ["John","johnsmith@mail.com","john00@mail.com"],
 * ["Mary","mary@mail.com"],
 * ["John","johnnybravo@mail.com"]]
 * 输出
 * [["John","john00@mail.com","john_newyork@mail.com","johnnybravo@mail.com","johnsmith@mail.com"],
 * ["Mary","mary@mail.com"],
 * ["John","johnnybravo@mail.com"],
 * ["John","johnnybravo@mail.com"]]
 * 预期结果
 * [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
 * ["Mary","mary@mail.com"],
 * ["John","johnnybravo@mail.com"]]
 * <p>
 * [["Alex","Alex5@m.co","Alex4@m.co","Alex0@m.co"],
 * ["Ethan","Ethan3@m.co","Ethan3@m.co","Ethan0@m.co"],
 * ["Kevin","Kevin4@m.co","Kevin2@m.co","Kevin2@m.co"],
 * ["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe2@m.co"],
 * ["Gabe","Gabe3@m.co","Gabe4@m.co","Gabe2@m.co"]]
 * 输出
 * [["Alex","Alex0@m.co","Alex4@m.co","Alex5@m.co"],
 * ["Ethan","Ethan0@m.co","Ethan3@m.co","Ethan3@m.co"],
 * ["Kevin","Kevin2@m.co","Kevin2@m.co","Kevin4@m.co"],
 * ["Gabe","Gabe0@m.co","Gabe2@m.co","Gabe3@m.co","Gabe4@m.co"]]
 * 预期结果
 * [["Alex","Alex0@m.co","Alex4@m.co","Alex5@m.co"],
 * ["Ethan","Ethan0@m.co","Ethan3@m.co"],
 * ["Gabe","Gabe0@m.co","Gabe2@m.co","Gabe3@m.co","Gabe4@m.co"],
 * ["Kevin","Kevin2@m.co","Kevin4@m.co"]]
 */
public class SolutionErr {
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> results = new ArrayList<>();
        for (List<String> account : accounts) {
            if (results.isEmpty()) {
                results.add(account);
                continue;
            }
            int size = results.size();
            for (int i = 0; i < size; i++) {
                List<String> arr = results.get(i);
                if (arr.get(0).equals(account.get(0))) {
                    int m = arr.size();
                    int n = account.size();
                    List<String> tmp1 = arr.subList(1, m);
                    List<String> tmp2 = account.subList(1, n);
                    ArrayList<String> all = new ArrayList<>();
                    all.addAll(tmp1);
                    all.addAll(tmp2);
                    List<String> collect = all.stream().distinct().collect(Collectors.toList());
                    int length = collect.size();
                    if (length <= m + n - 3) {
                        List<String> strs = new ArrayList<>();
                        strs.add(arr.get(0));
                        strs.addAll(collect);
                        results.set(i, strs);
                    }
                    continue;
                }
                if (i == size - 1) {
                    results.add(account);
                }
            }
        }
        for (List<String> result : results) {
            sortMails(result, 1);
        }
        return results;
    }

    public static void sortMails(List<String> mails, int start) {
        int size = mails.size();
        List<String> results = mails.subList(start, size);
        Collections.sort(results);
        for (int i = 1; i < size; i++) {
            mails.set(i, results.get(i - 1));
        }
    }

    public static void main(String[] args) {
        List<List<String>> results = new ArrayList<>();
        results.add(Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com"));
        results.add(Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com"));
        results.add(Arrays.asList("Mary", "mary@mail.com"));
        results.add(Arrays.asList("John", "johnnybravo@mail.com"));
        accountsMerge(results);
    }

    public List<List<String>> accountsMerge1(List<List<String>> accounts) {
        Map<String, Integer> emailToIndex = new HashMap<String, Integer>();
        Map<String, String> emailToName = new HashMap<String, String>();
        int emailsCount = 0;
        for (List<String> account : accounts) {
            String name = account.get(0);
            int size = account.size();
            for (int i = 1; i < size; i++) {
                String email = account.get(i);
                if (!emailToIndex.containsKey(email)) {
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email, name);
                }
            }
        }
        UnionFind uf = new UnionFind(emailsCount);
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();
            for (int i = 2; i < size; i++) {
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                uf.union(firstIndex, nextIndex);
            }
        }
        Map<Integer, List<String>> indexToEmails = new HashMap<Integer, List<String>>();
        for (String email : emailToIndex.keySet()) {
            int index = uf.find(emailToIndex.get(email));
            List<String> account = indexToEmails.getOrDefault(index, new ArrayList<String>());
            account.add(email);
            indexToEmails.put(index, account);
        }
        List<List<String>> merged = new ArrayList<List<String>>();
        for (List<String> emails : indexToEmails.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<String>();
            account.add(name);
            account.addAll(emails);
            merged.add(account);
        }
        return merged;
    }
}

class UnionFind {
    int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public void union(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }

    public int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
}
